import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author:gao
 * @date:2020/6/11
 * @time:11:12
 * @version:0.0.1
 * @description:none
 */


//739.每日温度

//单调栈，好妙啊
class Solution{
    public int[] dailyTemperatures(int[] T){
        Stack<Integer> stack = new Stack<>();
        int len = T.length;
        int[] ans = new int[len];
        for (int i=0;i<len;i++){
            while ((!stack.empty()&&T[i]>T[stack.peek()])){
                ans[stack.peek()]=i-stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return ans;
    }
}

//自己的解法，时间O（n）,但是效率不如官方单调栈解法
class Solution_five {
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        int[] ans = new int[len];
        int[] tmp = new int[101];
        ans[len-1] =0;
        tmp[T[len-1]]=len-1;
        //通过从后往前标记辅助数组，表示本数据已经有了，
        //然后从比本次遍历的数组元素大的辅助数组开始遍历，
        //直至找到数值大于当前且下表差最小的
        for(int i= len-2;i>=0;i--){
            int n = T[i];
            tmp[n] = i;
            boolean su =false;
            int ans_tmp =Integer.MAX_VALUE;
            for(int j= n+1;j<=100;j++){
                if(tmp[j]>i){
                    ans_tmp = Integer.min(ans_tmp,tmp[j]-i);
                    su =true;
                }
                if(su){
                    ans[i] = ans_tmp;
                }
            }
            if(!su){
                ans[i]=0;
            }
        }
        return ans;
    }
}
